/**
* @description: 788. 旋转数字
* @author hewei
* @date 2022/8/24 16:48
* @version 1.0
*/

public class RotatedDigits {

    public static void main(String[] args) {
        RotatedDigits rotatedDigits = new RotatedDigits();
        System.out.println(rotatedDigits.rotatedDigits(10));
    }

    int[] nums1 = {0, 1, 8};
    int[] nums2 = {2, 5, 6, 9};
    char[] chars;
    public int rotatedDigits(int n) {
        chars = String.valueOf(n).toCharArray();
        return process(0, chars.length, false, true, true);

    }

    public int process(int i, int n, boolean isNum, boolean invalid, boolean isLimit) {
        if (i == n) return isNum && !invalid ? 1 : 0;

        int res = 0;
        if (!isNum) res += process(i + 1, n, false, true, false);
        for (int a : nums1) {
            if ((!isNum && a == 0) || (isLimit && a > chars[i] - '0')) continue;
            res += process(i + 1, n, true, invalid, isLimit && a == chars[i] - '0');
        }
        for (int a : nums2) {
            if (isLimit && a > chars[i] - '0') continue;
            res += process(i + 1, n, true, false, isLimit && a == chars[i] - '0');
        }
        return res;
    }
}
